数据结构和算法 -- 树

Posted on   |   In   |     |  

最大最小值

python 里找 float 的最小值，float(‘-inf’)，最大值，float(‘inf’)
找 int 的最大最小值

1
2
3
import sys
max = sys.maxint
min = -sys.maxint-1

其它

class 里创建 helper 方法第一个参数传 self, 调用 self.helper()
python 的三元运算符，python 的 max 方法。

基础

概念

  • Root: The node at the top of the tree
  • Parent: When any node (except the root) has exactly one edge running upward to another node. The node above is called parent of the node.
  • Child: Any node may have one or more lines running downward to other nodes. These nodes below the given node called its children.
  • Edge: connection between one node to another.
  • Leaf: A node that has no children is called a leaf. There can be only one root in a tree but there can be many leaves.
  • Level: The level of a node is defined by 1 + the number of connections between the node and the root.
  • Path: – a sequence of nodes and edges connecting a node with a descendant.
  • Height of node – The height of a node is the number of edges on the longest downward path between that node and a leaf.
  • Height of tree –The height of a tree is the number of edges on the longest downward path between the root and a leaf.
  • Depth –The depth of a node is the number of edges from the node to the tree’s root node.

complexity

insertion, 平均 O(logN)，左树找到 SPOT,右树找到 SPOT,一次砍一半，就是 O(logN)
deletion,平均情况 O(logN)多一些，先搜索到元素，O(logN)，没找到就 end，找到，分 4 种，记录元素是 left 还是 right

  • leaf parent 对应指针指到 null
  • 仅有左边 child，parent 对应指针指到左 child,元素指针全部删除
  • 仅有右边 child，parent 对应指针指到右 child,元素指针全部删除
  • 有左右两个 child，先找 successor，就是右子树的最小严肃，从要删除的元素往下一路向左，找到最左元素，定为 successor，然后如果 successor 有右树，将其连到 parent 的左树上，successor 新的右树，连到被删除元素的右树上。

Binary search tree 二叉搜索树

二叉搜索树每个节点比其左子树元素大，比其右子树元素小。

The left subtree of a node contains only nodes with keys less than node’s key.
The right subtree of a node contains only nodes with keys greater than node’s key.

二叉搜索树的作用：保持元素顺序，相当于是一个排序好的 list，插入删除操作，比排序的 list 快，维护元素顺序或对元素排序时，非常适用。

Balanced binary tree 平衡树

树结构越接近一个链条，各操作就越像线性结构，就越失去了树结构独特的优势，所以引入了平衡树

遍历方法

  • 深度优先（DFS）
    先根(preorder)，中根(inorder)，后根(postorder)
  • 广度优先（BFS）
    优先遍历完同层，是一个 queue 结构，先 dequeue 根节点 q，按照层序 enqueue 其 children，visit(q)然后 dequeue 根部新根节点。继续 enqueue，重复刀 dequeue 空为止。所有 node 都被 enqueue 和 dequeue 一遍，复杂度是 O(2n)，即 O(n)

stack & DFS

先根(144.Binary Tree Preorder Traversal)

注意 conner case root==None 的时候返回的是[],不是 root(None)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []
        else:
            return [root.val]+self.preorderTraversal(root.left)+self.preorderTraversal(root.right)

中根(94.Binary Tree Inorder Traversal)

1
2
3
4
5
6
7
8
9
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []
        return self.inorderTraversal(root.left)+[root.val]+self.inorderTraversal(root.right)

后根(145.Binary Tree Postorder Traversal)

1
2
3
4
5
6
7
8
9
class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []
        return self.postorderTraversal(root.left)+self.postorderTraversal(root.right)+[root.val]

queue & BFS(102. Binary Tree Level Order Traversal)

Problem

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

遍历当前的 queue, 把每个 node value 存到 list，将每个 node 的 left 和 right node 存到 queue，遍历完后将当前 list 加进 result 里。
问题是怎么遍历当前 queue，通过纪录每个 layer（也就是 queue）的长度来实现。
corner case: root == None, return []

Time complexity: O(n)，每个 node enqueue 一次，dequeue 一次
Space complexity: O(n)，worst space,最后一次，满树，大概 O(n/2)

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def levelOrder(self, root):
    """
    :type root: TreeNode
    :rtype: List[List[int]]
    """
    if not root:
        return []
    q = deque([root])
    result = []
    while q:
        layer = []
        size = len(q)
        for i in range(size):
            node = q.popleft()
            layer.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(layer)
    return result

解题策略

Divide and conquer

树和图的很多问题，可以分解成子问题递归求解（divide and conquer），一般思路是综合节点本身，左子树，右子树三方的局部解得到全局解。

要注意的是，传节点的时候

  • 设置出口，ending case，一般是 node==None；
  • Recursive down
  • Return up
  • Current layer

构造递归的时候，可以 suppose all subtrees are handled.

特定路径的问题

关于寻找特定路径的问题，通常需要回溯思想，我们往往需要设计一个 helper function，传入当前节点和其它需要记录的参数。

树和其他数据结构的相互转换

树 –> 其它数据结构：树的遍历，合并局部解来得到全局解
其它数据结构 –> 树：递归将数据结构的两部分分别转换成子树，再合并。

寻找特定节点

此类题目通常会传入一个当前节点，要求找到与此节点具有一定关系的特定节点：例如前驱、后继、左／右兄弟等。

对于这类题目，首先可以了解一下常见特定节点的定义及性质。在存在指向父节点指针的情况下，通常可以由当前节点出发，向上倒推解决。如果节点没有父节点指针，一般需要从根节点出发向下搜索，搜索的过程就是DFS。

注意点

Error control:

  • 确定 node.left, node.right 是否为 None，尤其是 leverl order traversal 中。
  • connection between nodes 在原来的 tree 上更改箭头，这样更清楚要不要抛弃某些箭头。

例题

101. Symmetric Tree

Problem

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1

/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
'''
Solution:
- primitive idea: level order traversal, use deque, check popleft()==pop(), but should consider how to handle [1,2,2,null,3,null,3], the easiest way is to treat it as a complete tree, keep None there
    this is two-pass solution, with O(n) space complexity and O(n) time complexity
- make it one-pass
Followup:
- without stack: use recursive
'''
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        return self.helper(root.left, root.right)
    def helper(self, left, right):
        if not left or not right:
            if left == right:
                return True
            else:
                return False
        if left.val == right.val:
            return self.helper(left.left, right.right) and self.helper(left.right, right.left)
        return False
    '''
    # two-pass solution with deque
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        # level order traversal
        result=deque()
        queue=deque([root])
        while queue:
            size=len(queue)
            layer=deque()
            for i in range(size):
                node=queue.popleft()
                if not node:
                    layer.append(None)
                    continue
                layer.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
            result.append(layer)
        # pop root and last level(all None)
        result.popleft()
        result.pop()
        while result:
            layer=result.pop()
            while layer:
                if layer.pop()!=layer.popleft():
                    return False
        return True
        '''     
    '''
    # one-pass solution with deque
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True  
        queue=deque([root.left,root.right])
        while queue:
            left=queue.popleft()
            right=queue.pop()
            if not left and not right: continue
            if not left or not right or left.val!=right.val: return False
            queue.appendleft(left.left)
            queue.appendleft(left.right)
            queue.append(right.right)
            queue.append(right.left)
        return True
    '''

156. Binary tree upside down

Problem

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
For example:
Given a binary tree {1,2,3,4,5},
1
/ \
2 3
/ \
4 5
return the root of the binary tree [4,5,2,#,#,3,1].
4
/ \
5 2
/ \
3 1

Assumption: input tree is valid
Conner Case: Null root –> Null new root

Solution

Stack 解法

Time compexity: O(n)
Space complexity: O(n/2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
'''
Solution:
- with stack: store all nodes along the left path in a stack, and flit it.
    root=>root.left,
    root.left=>root.right,
    root.right=>root
- recursive: assume lower layers are handled (we can pass root.left as parameter and call the function till leftmost node), handle current layer only
Attention:
- draw connection between nodes at original tree, so that you won't forget to clear pointers after each flip, and transfer root control.
'''
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
def upsideDownBinaryTree(self, root):
    """
    :type root: TreeNode
    :rtype: TreeNode
    """
    if not root:
        return root
    stack = []
    # store all nodes along the path in stack
    while root:
        stack.append(root)
        root = root.left
    # start from leftmost leaf
    newRoot = stack.pop()
    head = newRoot
    while stack:
        parent = stack.pop()
        head.left = parent.right # parent
        head.right = parent
        head = parent
        parent.left = None
        parent.right = None
    return newRoot

Recursive 解法

Identical subproblem, lower level first
通过 root.left 过渡到下一个子问题，从下往上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def upsideDownBinaryTree(self, root):
    """
    :type root: TreeNode
    :rtype: TreeNode
    """
    # stop case
    if not root or not root.left:
        return root
    # assume all lower levels are handled
    newRoot = self.upsideDownBinaryTree(root.left)
    # handle current level
    root.left.left = root.right
    root.left.right = root
    root.left = None
    root.right = None
    return newRoot

98. Valid binary search tree

Problem

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Example 1:
2
/ \
1 3
Binary tree [2,1,3], return true.
Example 2:
1
/ \
2 3

Solution

Inorder traversal

根据二叉搜索树的性质，我们知道二叉搜索树中序遍历之后是一个 sorted list，所以最直观的方法就是中序遍历存到一个 list，然后看它是不是 sorted。这样的空间复杂度是 O(N)，时间复杂度由排序算法决定。

Global max

用 global max 能让空间复杂度变成 O(1)？这个还不知道。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        list = self.getList(root)
        max = float('inf')
        while list:
            node = list.pop()
            if node >= max:
                return False
            max = node
        return True
    def getList(self, root):
        if not root:
            return []
        return self.getList(root.left)+[root.val]+self.getList(root.right)

Range

分解子问题，每一个 node 都大于它的 left child 并且小于它的 right child。所以可以写一个 helper function，传入 (node, min, max) 来判断 node 在不在正确的区间里。主要问题如下：

  • how to compare cross-layer
  • how to get a valid range for each node
    implementation: pass parameter top-to-bottom, helper(current_node,min,max)

注意小知识点，python 里找 float 的最小值，float(‘-inf’)，最大值，float(‘inf’)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def isBST(root, max=float('inf'), min=float('-inf')):
            if not root:
                return True
            if root.val >= max or root.val <= min:
                return False
            return isBST(root.left, root.val, min) and isBST(root.right, max, root.val)
        return isBST(root)

333. Largest BST Subtree

Problem

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:
A subtree must include all of its descendants.
Here’s an example:
10
/ \
5 15
/ \ \
1 8 7
The Largest BST Subtree in this case is the highlighted one.
The return value is the subtree’s size, which is 3.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
'''
Solution:
    brute-force: O(n^2)
Followup: make it O(n)
    Current layer: if both left subtree and right subtree are BST and left.max<=root.val<=right.min,then current subtree is BST and size=left.size+right.size+1,else,current subtree is not BST and size=max(left.size,right.size)
    Recursive down:
        base case: if not root
        recursive case:
            left=recursive(root.left), right=recursive(root.right)
    Return up:
        return res which includes:
            - isBST: if current subtree is BST
            - max: max value of left subtree
            - min: min value of right subtree
'''
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    '''
    brute-force: O(n^2)
    def largestBSTSubtree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def isBST(root, max=float('inf'), min=float('-inf')):
            if not root:
                return True
            if root.val >= max or root.val <= min:
                return False
            return isBST(root.left, root.val, min) and isBST(root.right, max, root.val)
        def size(root):
            if not root:
                return 0
            return size(root.left) + size(root.right) + 1
        if isBST(root):
            return size(root)
        return max(self.largestBSTSubtree(root.left), self.largestBSTSubtree(root.right))
        '''
class Solution(object):
    def largestBSTSubtree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        class Result(object):
            def __init__(self,myMax=float('-inf'),myMin=float('inf')):
                self.isBST=True
                self.max=myMax
                self.min=myMin
                self.size=0
        def recursive(root):
            res=Result()
            # base case
            if not root:
                return res
            # recursive case
            left=recursive(root.left)
            right=recursive(root.right)
            res.max=max(root.val,right.max)
            res.min=min(root.val,left.min)
            # current layer
            if left.isBST and right.isBST and left.max<=root.val and right.min>=root.val:
                res.size=left.size+right.size+1
                res.isBST=True
            else:
                res.isBST=False
                res.size=max(left.size,right.size)
            return res
        res= recursive(root)  
        return res.size

298. Binary Tree Longest Consecutive Sequence

Problem

Given a binary tree, find the length of the longest consecutive sequence path.
The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).
For example,
1
\
3
/ \
2 4
\
5
Longest consecutive sequence path is 3-4-5, so return 3.
2
\
3
/
2
/
1
Longest consecutive sequence path is 2-3,not3-2-1, so return 2.

直接想到的是，preorder 遍历，得到 list，用 count 更新 current max。然而这是有问题的！以 example 为例，遍历后的 list 是 [1,3,2,4,5],它把 2,4 连起来了，但是 2,4 属于不同的分支，所以不能这么做。

换一种思路，用 recursion 的方法，左子树的 max length, 右子树的 max length，和本身目前的 max length，求最大值。

第一个传进去的是什么？float(‘inf’)

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
'''
recurse down
helper(node.left, global_max, node.val)
helper(node.right, global_max, node.val)
return up
max (curr_lengh, left_max_length, right_max_length)
current level
global_max = node.val == lastVal + 1 : length + 1 : 1
'''
class Solution(object):
    def longestConsecutive(self, root):
        if not root:
            return 0
        return self.helper(root, 1, float('inf'))
    def helper(self, node, global_max, lastVal):
        if not node:
            return global_max
        global_max = global_max + 1 if node.val == lastVal + 1 else 1
        return max(global_max, self.helper(node.left, global_max, node.val), self.helper(node.right, global_max, node.val))

待补充

trie or prefix tree，full binary tree，complete binary tree，heap

222. Count Complete Tree Nodes

Problem

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Solution

Time complexity: O(h^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
'''
Primitive idea:
    traversal, BFS, DFS(preorder, inorder, postorder), takes O(n) time.
Faster:
    List all posibilities of a complete trees and we can conlude there're two cases one is the height of left subtree equals that of right subtree, in this case, the right subtree is always full, another case is that the height of left subtree is smaller than that of right subtree, then the left subtree is full. It's easy to count the nodes of full tree.
    We can use recursive method to solve this problem. That is,
    if height(left)==height(right): count(root)=2**leftH-1+1+count(root.right)
    else: count(root)==2**rightH-1+1+count(root.left)
    Time complexity: O(logn^2)
Tips:
    1<<h is faster than 2**h but remember to use () due to precedence
    be careful about getHeight method if not root should return -1 instead of 0
'''
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def getHeight(root):
            if not root:
                return-1
            return getHeight(root.left) + 1
        # base case
        if not root:
            return 0
        # recursive case
        leftH = getHeight(root)
        rightH = getHeight(root.right) + 1
        # left subtree is full
        if leftH == rightH:
            return (1 << leftH) + self.countNodes(root.right)
        # right subtree is full
        else:
            return (1 << rightH) + self.countNodes(root.left)

270. Closest Binary Search Tree Value

Problem

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:
Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
'''
- Solution: keeps a global closest variable and update it when doing the search. Time complexity: O(logN). Space complexity: O(1)
'''
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def closestValue(self, root, target):
        """
        :type root: TreeNode
        :type target: float
        :rtype: int
        """
        if not root: return None
        closest=root.val
        diff=abs(root.val-target)
        while root:
            if abs(root.val-target)<diff:
                diff=abs(root.val-target)
                closest=root.val
            root=root.right if root.val<target else root.left
        return closest
    '''
    def closestValue(self, root, target):
        """
        :type root: TreeNode
        :type target: float
        :rtype: int
        """
        if not root: return None
        if not root.left and not root.right: return root.val
        def inorderTraversal(root):
            if not root: return []
            return inorderTraversal(root.left)+[root.val]+inorderTraversal(root.right)
        vals=inorderTraversal(root)
        for i in range(len(vals)):
            if target<vals[i]:
                if abs(target-vals[i])<abs(target-vals[i-1]):
                    return vals[i]
                else:
                    return vals[i-1]
        return vals[-1]
        '''

272. Closest Binary Search Tree Value II

Problem

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:
Given target value is a floating point.
You may assume k is always valid, that is: k ≤ total nodes.
You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
'''
assume k is smaller than the # of nodes in BST
Wrong solution:
    Recall Closest Binary Search Tree Value I, maybe we can maintain a k-size of diff priorityqueue and k-size of closest priorityqueue and do the pop and push the same way as problem I?
    -> We can do that but only when H>=k where H is the height of BST, but when H<k, we should add more values into closest, it's hard to decide or to track these nodes because we may need to access the predecessors.
    -> So we may think of two helper function getSuccessor, getPredecessor,
- Solution 1:
    - have an in-order traversal and get a sorted array, then find the closest value to the target in the sorted array, and look forward and backwards to get k closest values.
    - or, same idea, have two stacks one stores the values that are smaller than the target, and the other stores the values that are larger than the target, and finally merge it
    - O(n) time complexity
- Solution 2:
    - first find the closest value cur to target, while k<0, find the closest smaller value to the cur and the closest larger value to the cur, compare them to find the the closest value to the target and add it to the result list till there're k values in the result
    - O(klogn) time complexity
Corner case:
    - Solution 1 must consider case when target<0
'''
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque
class Solution(object):
    # O(klogn)
    def closestKValues(self, root, target, k):
        """
        :type root: TreeNode
        :type target: float
        :type k: int
        :rtype: List[int]
        """
        if not root: return None
        closest=self.getClosestVal(root,target)
        res=[closest.val]
        k-=1
        # merge k values
        s=self.getSmaller(root,closest.val)
        l=self.getLarger(root,closest.val)
        while k>0:
            if not s:
                res.append(l.val)
                l=self.getLarger(root,l.val)
            elif not l:
                res.append(s.val)
                s=self.getSmaller(root,s.val)
            elif abs(s.val-target)<abs(l.val-target):
                res.append(s.val)
                s=self.getSmaller(root,s.val)
            else:
                res.append(l.val)
                l=self.getLarger(root,l.val)
            k-=1;
        return res
    def getSmaller(self,root,t):
        s=None
        while root:
            if root.val<t:
                s=root
                root=root.right
            else:
                root=root.left
        return s
    def getLarger(self,root,t):
        l=None
        while root:
            if root.val>t:
                l=root
                root=root.left
            else:
                root=root.right  
        return l
    def getClosestVal(self,root,target):
        closest=root
        diff=abs(root.val-target)
        while root:
            if abs(root.val-target)<diff:
                diff=abs(root.val-target)
                closest=root
            root=root.right if root.val<target else root.left
        return closest
    '''
    # O(n)
    def closestKValues(self, root, target, k):
        """
        :type root: TreeNode
        :type target: float
        :type k: int
        :rtype: List[int]
        """
        if not root: return None
        def dfs(root):
            if not root: return []
            return dfs(root.left)+[root.val]+dfs(root.right)
        values=dfs(root)
        # get smaller values and larger values
        res,smaller,larger=[],[],[]
        for v in values:
            if v<target:
                smaller.append(v)
            elif v>target:
                larger.append(v)
            else:
                res.append(v)
                k-=1
        # merge k values
        if target<0:
            smaller=smaller[::-1]
        larger=larger[::-1]
        while k>0:
            if not smaller:
                res.append(larger.pop())
            elif not larger:
                res.append(smaller.pop())
            elif abs(smaller[-1]-target)<abs(larger[-1]-target):
                res.append(smaller.pop())
            else:
                res.append(larger.pop())
            k-=1;
        return res
        '''

366. Find Leaves of Binary Tree

Problem

Given a binary tree, collect a tree’s nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example:
Given binary tree
1
/ \
2 3
/ \
4 5
Returns [4, 5, 3], [2], [1].

Explanation:
1.Removing the leaves [4, 5, 3] would result in this tree:

  1
 /
2

2.Now removing the leaf [2] would result in this tree:

1

3.Now removing the leaf [1] would result in the empty tree:

[]

Returns [4, 5, 3], [2], [1].

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
'''
Solution:
    brute-force
    string encoding(preorder): 124##5##3##
Followup: make it O(n)
    nodes with the same height should be leaves for each turn
'''
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    '''
    def findLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return []
        def getHeight(root):
            if not root: return 0
            return max(getHeight(root.left),getHeight(root.right))+1
        def traverse(root):
            global res
            if not root:
                return 0
            lev=max(traverse(root.left),traverse(root.right))+1
            res[lev-1].append(root.val)
            return lev
        global res
        h=getHeight(root)
        res=[list() for i in range(h)]
        traverse(root)
        return res
        '''
    def findLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        def traverse(root, res):
            if not root:
                return 0
            lev = max(traverse(root.left, res), traverse(root.right, res)) + 1
            res[lev].append(root.val)
            return lev
        res = collections.defaultdict(list)
        traverse(root, res)
        return res.values()

307. Range Sum Query - Mutable (Binary indexed tree)

Problem

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
'''
update: O(1)
sumRange: O(n)
class NumArray(object):
    def __init__(self, nums):
        """
        initialize your data structure here.
        :type nums: List[int]
        """
        self.nums=nums
    def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: int
        """
        self.nums[i]=val
    def sumRange(self, i, j):
        """
        sum of elements nums[i..j], inclusive.
        :type i: int
        :type j: int
        :rtype: int
        """
        return sum(self.nums[i:j+1])
        '''
'''
Use self.bit to represent Binary Indexed Tree. Section sums are stored in self.c[1..len(nums)]. x & -x is lowbit function, which will return x's rightmost bit 1, e.g. lowbit(7) = 1, lowbit(20) = 4.
Both update and sumRange takes O(logn) time.
See http://www.cnblogs.com/grandyang/p/4985506.html
'''
class NumArray(object):
    def __init__(self, nums):
        self.n = len(nums)
        self.nums, self.bit = [0] * (self.n + 1), [0] * (self.n + 1)
        for i,n in enumerate(nums):
            self.update(i,n)
    def update(self, i, val):
        diff, self.nums[i] = val - self.nums[i], val
        i += 1
        while i <= self.n:
            self.bit[i] += diff
            i += (i & -i)
    def sumRange(self, i, j):
        res, j = 0, j + 1
        while j:
            res += self.bit[j]
            j -= (j & -j)
        while i:
            res -= self.bit[i]
            i -= (i & -i)
        return res
徐阿衡 wechat
欢迎关注：徐阿衡的微信公众号
客官，打个赏呗~